#include <binary_tree.hpp>
#include <queue>
//------------------------------------------
// function about BinaryTree  ---------------
//------------------------------------------


//Node
BinaryTree_Node::BinaryTree_Node(ListData Data)
{
  data=Data;
  leftNode=nullptr;
  rightNode=nullptr;
}

BinaryTree_Node::~BinaryTree_Node()
{
  delete this->leftNode;
  delete this->rightNode;
}


BinaryTree_Node::BinaryTree_Node(BinaryTree_Node* preNode)
:leftNode(nullptr),rightNode(nullptr)
{
  this->data=preNode->data;    //data copy over
  if(preNode->leftNode!=nullptr)
  {
   this->leftNode=new BinaryTree_Node(preNode->leftNode);
  }
  else
  {
   this->leftNode=nullptr;
  }

  if(preNode->rightNode!=nullptr)
  {
   this->rightNode=new BinaryTree_Node(preNode->rightNode);
  }
  else
  {
    this->rightNode=nullptr;
  }
}

void BinaryTree_Node::PreOrderTraverse()
{
    this->data.show();

  if(this->leftNode!=nullptr)
  {
     this->leftNode->PreOrderTraverse();
  }
  

  if(this->rightNode!=nullptr)
  {
     this->rightNode->PreOrderTraverse();
  }
}


void BinaryTree_Node::InOrderTraverse()
{
 if(this->leftNode!=nullptr)
 {
  this->leftNode->InOrderTraverse();
 } 
 this->data.show();
 if(this->rightNode!=nullptr)
 {
  this->rightNode->InOrderTraverse();
 }
}


void BinaryTree_Node::PostOrderTraverse()
{
 if(this->leftNode!=nullptr)
 {
   this->leftNode->PostOrderTraverse();
 }
 if (this->rightNode!=nullptr) 
 {
   this->rightNode->PostOrderTraverse();
 }
 this->data.show();
}

void BinaryTree_Node::LevelOrderTraverse()
{
   std::queue<BinaryTree_Node*> TraverseQueue;
   TraverseQueue.push(this);
   while (!TraverseQueue.empty()) {
   TraverseQueue.front()->data.show(); 
   if(TraverseQueue.front()->leftNode!=nullptr)
   {
   TraverseQueue.push(TraverseQueue.front()->leftNode);
   }
   if(TraverseQueue.front()->rightNode!=nullptr)
   {
   TraverseQueue.push(TraverseQueue.front()->rightNode);
   }
   TraverseQueue.pop();
   }
}

int BinaryTree_Node::GetDepth()
{
  int m=0,n=0,res=0;
  if(leftNode!=nullptr)
  {
  m=leftNode->GetDepth();
  }
  if(rightNode!=nullptr)
  {
  n=rightNode->GetDepth();
  }
  res=m>n?m:n;
  res++;
  return res;
}


int BinaryTree_Node::NodeCount()
{
  int m=0,n=0;
  if(leftNode!=nullptr)
  {
  m=leftNode->NodeCount();
  }
  if(rightNode!=nullptr)
  {
  n=rightNode->NodeCount();
  }
  return m+n+1;
}
   
   
int BinaryTree_Node::LeadCount()
{
  int m=0,n=0;
  if(leftNode==nullptr&&rightNode==nullptr)
  {
    return 1;
  }
 if(leftNode!=nullptr)
  {
  m=leftNode->LeadCount();
  }
  if(rightNode!=nullptr)
  {
  n=rightNode->LeadCount();
  }
  return m+n;

}


//Tree

BinaryTree::BinaryTree(ListData Data)
:root(nullptr)
{
  root=new BinaryTree_Node(Data);
}

BinaryTree::~BinaryTree()
{
 delete root;
}


void BinaryTree::PreOrderTraverse()
{
  root->PreOrderTraverse();
}



void BinaryTree::InOrderTraverse()
{
 root->InOrderTraverse();
}



void BinaryTree::PostOrderTraverse()
{
 root->PostOrderTraverse();
}


void BinaryTree::LevelOrderTraverse()
{
 root->LevelOrderTraverse();
}


void BinaryTree::Insert(ListData res)
{
  BinaryTree_Node* tmp=root;

//the smaller is on the ringht
  while(1)
  {
   if(res<(tmp->data))
   {
    if(tmp->rightNode==nullptr)
    {
       BinaryTree_Node* newNode=new BinaryTree_Node(res);
       tmp->rightNode=newNode;
       break;
    }
    else
    {
      tmp=tmp->rightNode;
    }
   }
   else if (res == (tmp->data)) { break; } //data is unique
   else
   {
     if(tmp->leftNode==nullptr)
     {
       BinaryTree_Node* newNode=new BinaryTree_Node(res);
       tmp->leftNode=newNode;
       break;
     }
     else
     {
        tmp=tmp->leftNode;
     }  
   }
  }
}


void BinaryTree::Delete(ListData res)//删除节点之后用原节点的右节点替换（如果有右节点的话），没有就用左节点替换
{
  BinaryTree_Node** ptmp=&root;//tmp和整个二叉树结构中某个节点指向相同位置，ptmp指向这个节点的位置而不是tmp的位置 
  BinaryTree_Node* tmp=root;

  while(1)
  {
   if(res<(tmp->data))
   {
    if(tmp->rightNode==nullptr)
    {
      std::cout<<"data not exit!";
       break;
    }
    else
    {
      ptmp=&((*ptmp)->rightNode);
      tmp=tmp->rightNode;
    }
   }
   else if (res==(tmp->data)) //find equal node
   {
      if(tmp->leftNode==nullptr&&tmp->rightNode==nullptr)
      {
        delete tmp;
        *ptmp=nullptr;
      }
      else if(tmp->leftNode==nullptr&&tmp->rightNode!=nullptr)
      {
         *ptmp=(*ptmp)->rightNode;
         tmp->rightNode=nullptr;
         delete tmp;
      }
      else if(tmp->leftNode!=nullptr&&tmp->rightNode==nullptr)
      {
        *ptmp=(*ptmp)->leftNode;
        tmp->leftNode=nullptr;
        delete tmp;
      }
      else 
      {
        BinaryTree_Node* tmp2=tmp;
       tmp2=tmp->rightNode;
        while(1)
        {
         if(tmp2->leftNode==nullptr)
         {
          break;
         }
         tmp2=tmp2->leftNode;        //tmp2现在是tmp右子树最左的节点，现在要把tmp的左子树迁移到最左节点的左节点上
        }
        tmp2->leftNode=tmp->leftNode;//迁移完毕
        //delete
        *ptmp=(*ptmp)->rightNode;//调整二叉树结构中指向的位置
        tmp->rightNode=nullptr;//清除原位置
        tmp->leftNode=nullptr;
        delete tmp;
      }
      break;
   }
   else
   {
     if(tmp->leftNode==nullptr)
     {
      std::cout<<"data not exit!";
       break;
     }
     else
     {
        ptmp=&((*ptmp)->leftNode);
        tmp=tmp->leftNode;
     }  
   }
  }
}


BinaryTree::BinaryTree(const BinaryTree &preTree)
:root(nullptr)
{
  root=new BinaryTree_Node(preTree.root); //create root over
}


BinaryTree& BinaryTree::operator=(const BinaryTree &preTree)
{
 delete root;
 this->root=new BinaryTree_Node(preTree.root);
 return *this;
}


int BinaryTree::GetDepth()
{
  return root->GetDepth();
}

int BinaryTree::NodeCount()
{
  return root->NodeCount();
}

int BinaryTree::LeadCount()
{
 return root->LeadCount();
}
